import java.util.LinkedList;
import java.util.Queue;

public class Dota2 {

//    649. Dota2 参议院
//    https://leetcode.cn/problems/dota2-senate/description/



    public static void main(String[] args) {
        System.out.println(predictPartyVictory("RDD"));
    }


//    贪心算法

    /**
     * 时间复杂度：O(n)，其中 n 是字符串senate 的长度。在模拟整个投票过程的每一步，我们进行的操作的时间复杂度均为 O(1)
     * 并且会弹出一名天辉方或夜魇方的议员。由于议员的数量为 n，因此模拟的步数不会超过 n，时间复杂度即为 O(n)
     *
     * 空间复杂度：O(n)，即为两个队列需要使用的空间。
     * @param senate
     * @return
     */
    public static String predictPartyVictory(String senate) {
//        定义两个队列 分别存R 和 D 的下标  再通过下标来判断 顺序
        Queue<Integer> r = new LinkedList<>();
        Queue<Integer> d = new LinkedList<>();

        int length = senate.length();
        for (int i = 0; i < length; i++) {
//            通过下标拿到字符
            if (senate.charAt(i) == 'R') {
                r.offer(i);
            }else {
                d.offer(i);
            }
        }

//        但队列其中有一列变为空时 结束循环
        while (!r.isEmpty() && !d.isEmpty()) {
            int rPoll = r.poll();
            int dPoll = d.poll();
            if (rPoll < dPoll) {
                r.offer(rPoll + length); // 这里加length  是让R(下标)进入下一轮  不在参加本轮判断
            }else {
                d.offer(dPoll + length);
            }
        }
        return r.isEmpty()? "Dire" : "Radiant";
    }
}
